package com.chj.chuji.tijie05;

//https://zhuanlan.zhihu.com/p/54277674
public class TwoSum {
	public static int[] twoSum(int[] numbers, int target) {
		int j = numbers.length - 1;
		int[] output = new int[2];
		if (numbers[0] >= 0)
			while (numbers[j] > target && j >= 0)
				--j;
		// System.out.println("j="+j);
		for (; j >= 0; j--) {
			int diff = target - numbers[j];
			int right = j;
			int left = 0;
			// System.out.println("diff="+diff);
			while (left < right) {
				int mid = (left + right) / 2;
				// System.out.println("mid:" +mid+", left:"+left+", right:"+right);
				if (numbers[mid] == diff) {
					output[0] = mid + 1;
					output[1] = j + 1;
					return output;
				}
				if (numbers[mid] > diff) {
					right = mid;
					// System.out.println("check left part, right = "+right);
				} else {
					left = mid + 1;
					// System.out.println("check right part, left = "+left);
				}
			}
		}
		return output;
	}

	public static void main(String[] args) {
		int target = 9;
		int[] numbers = new int[] { 2, 7, 11, 15 };

		System.out.println(twoSum(numbers, target)[0] + " : " + twoSum(numbers, target)[1]);

		int target2 = 7;
		numbers = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
		System.out.println(twoSum(numbers, target2)[0] + " : " + twoSum(numbers, target2)[1]);

	}
}
